package lime2.ca.treeplain;

import java.io.Serializable;
import java.net.InetAddress;
import java.net.UnknownHostException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import lime2.LimeServerID;
import lime2.Location;

/**
 * The abstract graph of network layout
 * @author Xing Jiankuan
 *
 */
public class Graph {
	private static final long INFINITY = Long.MAX_VALUE;
	private Vertex vertexArr[];
	private long adjMatrix[][];
	private CastTree castTree;
	private Vertex dummyRoot;
	
	public Graph(Mesh mesh) {
		int serversNum = mesh.serversNum;
		vertexArr = new Vertex[serversNum];
		adjMatrix = new long[serversNum][serversNum];
		for (int j = 0; j < serversNum; j++)
			for (int k = 0; k < serversNum; k++)
				adjMatrix[j][k] = INFINITY;
		dummyRoot = new Vertex(Location.HERE.getID());
		dummyRoot.children = new ArrayList<Vertex>();
		init(mesh);
	}
	
 
	/**
	 * Initialize the graph by the specified mesh and create vertices and edges
	 * @param mesh
	 * @author Xing Jiankuan
	 */
	private void init(Mesh mesh) {
		synchronized (mesh) {
			Set<LimeServerID> keySet = mesh.serversMap.keySet();
			// the vertex keep the same index as their LimeServerID in Mesh.serversMap,
			// Therefore, it is convenient to find a vertex' adjacent.
			for(LimeServerID server: keySet) {
				int index = mesh.serversMap.get(server);
				vertexArr[index] = new Vertex(server, index);
			}
			
			for (int i = 0; i < vertexArr.length; i++) {
				for (int j = 0; j < vertexArr.length; j++) {
					addEdge(vertexArr[i], vertexArr[j], mesh.delayMatrix[i][j]);
				}
			}
		}
	}
	
	/**
	 * Acquire the Minimal Spanning Tree based on this graph
	 * @return cast tree
	 * @author Xing Jiankuan
	 */
	public CastTree getMiniSpanningTree() {
		if (castTree == null)
			createMiniSpanningTree();
		return castTree;
	}
	
//	Graph() throws UnknownHostException {
//		//for test
//		LimeServerID id1 = new LimeServerID(InetAddress.getByName("192.168.20.1"), 50);
//		LimeServerID id2 = new LimeServerID(InetAddress.getByName("192.168.20.2"), 50);
//		LimeServerID id3 = new LimeServerID(InetAddress.getByName("192.168.20.3"), 50);
//		LimeServerID id4 = new LimeServerID(InetAddress.getByName("192.168.20.4"), 50);
//		LimeServerID id5 = new LimeServerID(InetAddress.getByName("192.168.20.5"), 50);
//		LimeServerID id6 = new LimeServerID(InetAddress.getByName("192.168.20.6"), 50);
//		LimeServerID id7 = new LimeServerID(InetAddress.getByName("192.168.20.7"), 50);
//		LimeServerID id8 = new LimeServerID(InetAddress.getByName("192.168.20.8"), 50);
//		Location.HERE = new Location(id1);
//		
//		vertexArr = new Vertex[8];
//		adjMatrix = new long[8][8];
//		for (int j = 0; j < 8; j++)
//			for (int k = 0; k < 8; k++)
//				adjMatrix[j][k] = INFINITY;
//		dummyRoot = new Vertex(Location.HERE.getID());
//		dummyRoot.children = new ArrayList<Vertex>();
//		vertexArr[0] = new Vertex(id1, 0);
//		vertexArr[1] = new Vertex(id2, 1);
//		vertexArr[2] = new Vertex(id3, 2);
//		vertexArr[3] = new Vertex(id4, 3);
//		vertexArr[4] = new Vertex(id5, 4);
//		vertexArr[5] = new Vertex(id6, 5);
//		vertexArr[6] = new Vertex(id7, 6);
//		vertexArr[7] = new Vertex(id8, 7);
//		Random random = new Random();
//		random.setSeed(1);
//		for (int i = 0; i < vertexArr.length; i++) {
//			for (int j = 0; j < vertexArr.length; j++) {
//				addEdge(vertexArr[i], vertexArr[j], 1000 + random.nextInt(1000));
//			}
//		}
//	}
//	
//	public static void main(String[] args) throws UnknownHostException {
//		Graph g = new Graph();
//		CastTree tree = g.createMiniSpanningTree();
//		System.out.println(tree);
//		LimeServerID[] ids = {g.vertexArr[2].server, g.vertexArr[4].server,
//				g.vertexArr[3].server};
//		tree = g.getMiniSpanningTree(ids);
//		System.out.println(tree);
//	}
	
	
	/**
	 * Acquire the Minimal Spanning Tree based on this graph.
	 * This method guarantees that any leaf vertex of the tree
	 * belongs to the set of given <code>servers</code>.
	 * @param servers the servers that the tree has to reached
	 * @return cast tree
	 * @author Xing Jiankuan
	 */
	public CastTree getMiniSpanningTree(LimeServerID[] servers) {
		CastTree tree = getMiniSpanningTree();
		
		//construct a set
		HashSet<LimeServerID> serversSet = new HashSet<LimeServerID>();
		for(LimeServerID server: servers) {
			serversSet.add(server);
		}
		 
		dummyRoot.children.clear();
		dummyRoot.children.add(tree.root);
		//prune the tree
		recursivePruneTree(tree.root, serversSet);
		
		tree.root = dummyRoot.children.get(0);
		
		return tree;
	}
	
	private void recursivePruneTree(Vertex currVert, HashSet<LimeServerID> serversSet) {
		if(currVert.children == null || currVert.children.isEmpty()) {
			//current vertex is a leaf
			if(!serversSet.contains(currVert.server)) {
				//the currVert.parent never be null since dummyRoot
				currVert.parent.children.remove(currVert);
				currVert.parent = null;
			} 
		} else {
			//prune sub vertices
			ArrayList<Vertex> children = new ArrayList<Vertex>(currVert.children);
			for(Vertex subVert: children)
				recursivePruneTree(subVert, serversSet);
			
			//after pruning, current vertex may become a leaf
			if(currVert.children.isEmpty() && !serversSet.contains(currVert.server)) {
				currVert.parent.children.remove(currVert);
				currVert.parent = null;
			}
		}
	}

	/**
	 * Create a minimal spanning tree 
	 * @return
	 * @author Xing Jiankuan
	 */
	private CastTree createMiniSpanningTree() {
		//minimum priority queue
		TreeSet<Vertex> pq = new TreeSet<Vertex>(new VertexKeyComparator());
		castTree = new CastTree();
		
		//initialization
		for(int i = 0; i < vertexArr.length; i++) {
			Vertex v = vertexArr[i];
			if(v.server.equals(Location.HERE.getID())) {
				v.key = 0;	
				castTree.root = v;
			}else{
				v.key = INFINITY;
			}
			v.parent = null;
			v.children = null;
			pq.add(v);
		}
		
		while (!pq.isEmpty()) {
			Vertex currentVert = pq.pollFirst();
			//find all its adjacent vertex
			for(int i = 0; i < vertexArr.length; i++) {
				Vertex v = vertexArr[i];
				if(pq.contains(v) && //not self 
				   adjMatrix[currentVert.index][i] != INFINITY && // connected
				   adjMatrix[currentVert.index][i] < v.key) { // has a lower cost
					
					//reinsert the vertex whose key is changed into PQ
					//to change its order.
					// CAUTION: you should never remove v from pq after change its
					// key because pq locate v in internal tree by comparator's
					// comparisons. After key's change, pq may not find the
					// correct position of v and leads to a mess.
					pq.remove(v);
					v.key = adjMatrix[currentVert.index][i];
					pq.add(v);
					
					//add sub nodes
					v.parent = currentVert;
				}
			}
		}
		
		for(int i = 0; i < vertexArr.length; i++) {
			Vertex parent = vertexArr[i].parent;
			if(parent != null) {
				if(parent.children == null)
					parent.children = new ArrayList<Vertex>();
				parent.children.add(vertexArr[i]);
			}
		}
		return castTree;
	}

	private void addEdge(Vertex src, Vertex dest, long cost) {
		adjMatrix[src.index][dest.index] = cost;
	}

	
}

class Vertex implements Serializable {

	private static final long serialVersionUID = -582902517096787902L;
	public LimeServerID server;
	public transient int index;
	public transient long key;
	public ArrayList<Vertex> children;
	public Vertex parent;

	/**
	 * 
	 * @param index the lime server's index in mesh
	 * 
	 */
	public Vertex(LimeServerID id) {
		this.server = id;
		this.index = Mesh.getInstance().serversMap.get(id);
	}
	
	/**
	 * 
	 * @param s Lime server id
	 * @param index the lime server's index in mesh
	 * 
	 */
	public Vertex(LimeServerID id, int index) {
		this.server = id;
		this.index = index;
	}
	
	public boolean equals(Object o) {
		if(o!= null && o instanceof Vertex) {
			Vertex that = (Vertex)o;
			return this.server.equals(that.server);
		} else
			return false;
	}
	
	public void addChild(Vertex v) {
		if(this.children == null)
			this.children = new ArrayList<Vertex>();
		
		this.children.add(v);
		v.parent = this;
	}
	
	public String toString() {
		String strKey = key == Long.MAX_VALUE?"INF":String.valueOf(key);
		return server + "(" + strKey + ")";
	}
	
	public int hashCode() {
		return server.hashCode();
	}
}

class VertexKeyComparator implements Comparator<Vertex> {

	@Override
	public int compare(Vertex v1, Vertex v2) {
		if (v1.key < v2.key)
			return -1;
		else if(v1.key > v2.key)
			return 1;
		else 
			return v1.server.toString().compareTo(v2.server.toString());
	}
}

class CastTree implements Serializable {

	private static final long serialVersionUID = -1302160592742971428L;
	
	public Vertex root;
	
	@Override
	public String toString() {
		if(root == null)
			return "EMPTY_CAST_TREE";
		StringBuffer sb = new StringBuffer();
		recursiveToString(root, "", sb);
		return sb.toString();
	}
	
	/**
	 * Recursive generate the text representation of tree 
	 * @param cur
	 * @param indent
	 * @param sb
	 * @author Xing Jiankuan
	 */
	private void recursiveToString(Vertex cur, String indent, StringBuffer sb) {
		sb.append(indent);
		sb.append(cur.server.toString());
		sb.append("\n");
		if(cur.children != null && !cur.children.isEmpty()) {
			indent = indent + "\t";
			for(Vertex child: cur.children) {
				recursiveToString(child, indent, sb);
			}
		}
	}
}






